package com.leetcode;

import java.util.HashMap;

/**
 * 给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。
 * 子数组是数组中元素的连续非空序列。
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,1,1], k = 2
 * 输出：2
 */
public class No560 {
    /**
     * 方法1: 暴力枚举, 时间复杂度O(n^2), 空间复杂度O(1)
     * 遍历数组, 以每个元素为起点, 枚举所有可能的子数组, 统计和为k的子数组的个数
     */

    /**
     * 方法2: 前缀和+哈希表, 时间复杂度O(n), 空间复杂度O(n)
     * 遍历数组, 计算之前所有元素的和, 并将前缀和出现的次数存储在哈希表中
     * 遍历数组, 假设当前元素为nums[i], 则需要找到之前出现过的前缀和为preSum[i]-k的位置j
     * 则[j+1, i]的子数组和为k, 统计所有这样的位置j的个数即可
     */

    public int subarraySum(int[] nums, int k) {
        int res = 0;
        int sum = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int num : nums) {
            sum += num;
            if (map.containsKey(sum - k)) {
                res += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return res;
    }
}
